/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/binary-tree-longest-consecutive-sequence-ii
   @Language: C++
   @Datetime: 19-06-11 09:58
   */

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

// Method 1, Time 101ms
class Solution {
	int path(TreeNode *root, int diff){
		if(root==NULL) return 0;
		int left=0, right=0;
		if(root->left && root->left->val==root->val+diff) left=1+path(root->left,diff);
		if(root->right && root->right->val==root->val+diff) right=1+path(root->right,diff);
		return max(left,right);
	}
public:
	/**
	 * @param root: the root of binary tree
	 * @return: the length of the longest consecutive sequence path
	 */
	int longestConsecutive2(TreeNode * root) {
		// write your code here
		if(root==NULL) return 0;
		int len=path(root,1)+path(root,-1)+1;
		return max(len,max(longestConsecutive2(root->left),longestConsecutive2(root->right)));
	}
};

// Method 2, Time 50ms
class Solution {
	pair<int,int> path(TreeNode *root, TreeNode *parent, int &mx){
		if(root==NULL) return {0,0};
		auto left=path(root->left,root,mx);
		auto right=path(root->right,root,mx);
		mx=max(mx,left.first+right.second+1);
		mx=max(mx,left.second+right.first+1);
		int increase=0, decrease=0;
		if(root->val==parent->val+1) increase=max(left.first,right.first)+1;
		if(root->val==parent->val-1) decrease=max(left.second,right.second)+1;
		return {increase,decrease};
	}
public:
	/**
	 * @param root: the root of binary tree
	 * @return: the length of the longest consecutive sequence path
	 */
	int longestConsecutive2(TreeNode * root) {
		// write your code here
		int mx=0;
		path(root,root,mx);
		return mx;
	}
};
